//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 二叉搜索树
 * 若左节点不为空，那么他的左节点所有根的值都小于根节点
 * 若右节点不为空，那么他的右节点的所有根的值都大与根节点
 * 不会存在有俩个一样值的节点在二叉搜索树中
 */
public class map {
    TreeNode root = null;

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public map() {
    }

    //递归
    public void push(TreeNode root, int val) {
        if (root == null) {
            this.root = new TreeNode(val);
        } else if (root.val > val) {
            if (root.left == null) {//判断该节点若为叶子节点，那么他就是插入节点的父节点
                root.left = new TreeNode(val);
                return;
            }
            this.push(root.left, val);//节点大val那么就往左边走
        } else {
            if (root.right == null) {
                root.right = new TreeNode(val);
                return;
            }
            this.push(root.right, val);//节点小于val那么就往值更大的右边走
        }
    }

    //在指定节点后插入
    public void insert(TreeNode root, int val) {
        if (root == null) {
            root = new TreeNode(val);
        }
        TreeNode tmp;
        if (root.val > val) {
            if (root.left == null || root.left.val < val) {
                tmp = root.left;
                root.left = new TreeNode(val);
                root.left.left = tmp;
                return;
            }

            this.insert(root.left, val);
        } else {
            if (root.right == null || root.right.val > val) {
                tmp = root.right;
                root.right = new TreeNode(val);
                root.right.right = tmp;
                return;
            }

            this.insert(root.right, val);
        }

    }

    public Boolean del(TreeNode root, int key) {
        TreeNode prev = root;//记录被删除节点的父节点
        TreeNode cur = root;//为被删除节点

        //找到删除的节点所在的节点 key
        while(cur != null) {
            if (cur.val > key) {
                prev = cur;
                cur = cur.left;
            } else {
                if (cur.val == key) {
                    break;
                }
                prev = cur;
                cur = cur.right;
            }
        }

        if (cur == null) {//不存在key
            return false;
        } else {//删除 从被删除节点
            if (cur.left == null) {//左节点为空
                if (cur == prev) {
                    cur = cur.right;
                    this.root = cur;
                } else if (prev.right == cur) {
                    prev.right = cur.right;
                } else {
                    prev.left = cur.right;
                }
            } else if (cur.right == null) {//右节点为空
                if (cur == prev) {
                    cur = cur.left;
                    this.root = cur;
                } else if (prev.right == cur) {
                    prev.right = cur.left;
                } else {
                    prev.left = cur.left;
                }
            } else {//左右不为空
                TreeNode cur1 = cur.left;
                TreeNode prev1;
                for(prev1 = cur.left; cur1.right != null; cur1 = cur1.right) {
                }//找打有左树最大的树 也就是左树的最右节点
                if (cur1 == prev1) {//左树没有右支树
                    cur.val = cur1.val;
                    cur.left = cur1.left;
                } else {
                    cur.val = cur1.val;
                    //虽然cur1没有了右节点，但是他仍然可能右左节点那么就要连起来他的左节点
                    prev1.right = cur1.left;
                }
            }
            return true;
        }
    }

    private void swapChildVal(TreeNode root) {
        int tmp = root.left.val;
        root.left.val = root.right.val;
        root.right.val = tmp;
    }

    void preOrder(TreeNode root) {
        if (root != null) {
            System.out.print(root.val + " ");
            this.preOrder(root.left);
            this.preOrder(root.right);
        }

    }

    //会将空节点几位null
    public List<List<String>> levelOrder(TreeNode root) {
        List<List<String>> arr = new LinkedList();
        if (root == null) {
            return arr;
        } else {
            Queue<TreeNode> queue = new LinkedList();
            queue.offer(root);

            while(!queue.isEmpty()) {
                int size = queue.size();

                LinkedList tmpL;
                for(tmpL = new LinkedList(); size != 0; --size) {
                    TreeNode tmp = (TreeNode)queue.poll();
                    if (tmp != null) {
                        tmpL.add("" + tmp.val);
                        queue.offer(tmp.left);
                        queue.offer(tmp.right);
                    } else {
                        tmpL.add("null");
                    }
                }

                arr.add(tmpL);
            }

            return arr;
        }
    }

    public List<List<Integer>> levelOrder1(TreeNode root) {
        List<List<Integer>> arr = new LinkedList();
        if (root == null) {
            return arr;
        } else {
            Queue<TreeNode> queue = new LinkedList();
            queue.offer(root);

            while(!queue.isEmpty()) {
                int size = queue.size();

                LinkedList tmpL;
                for(tmpL = new LinkedList(); size != 0; --size) {
                    TreeNode tmp = (TreeNode)queue.poll();
                    tmpL.add(tmp.val);
                    if (tmp.left != null) {
                        queue.offer(tmp.left);
                    }

                    if (tmp.right != null) {
                        queue.offer(tmp.right);
                    }
                }

                arr.add(tmpL);
            }

            return arr;
        }
    }


}
